package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import org.junit.Test;

public class P剑指Offer12矩阵中的路径 {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        // 这种是先判断条件，再进去递归
        public boolean exist(char[][] board, String word) {
            int h = board.length, w = board[0].length;
            boolean[][] visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }

        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
            visited[i][j] = true;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            boolean result = false;
            if (board[i][j] == s.charAt(k)) {
                if(k==s.length()-1){
                    return true;
                }
                for (int[] dir : directions) {
                    int newi = i + dir[0], newj = j + dir[1];
                    if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                        if (!visited[newi][newj]) {
                            boolean flag = check(board, visited, newi, newj, s, k + 1);
                            if (flag) {
                                result = true;
                                break;
                            }
                        }

                    }
                }
            }
            visited[i][j] = false;
            return result;
        }


        // 这种是一股脑进去递归，再判断条件
//        public boolean exist(char[][] board, String word) {
//            int h = board.length, w = board[0].length;
//            boolean[][] visited = new boolean[h][w];
//            for (int i = 0; i < h; i++) {
//                for (int j = 0; j < w; j++) {
//                    boolean flag = check(board, visited, i, j, word, 0);
//                    if (flag) {
//                        return true;
//                    }
//                }
//            }
//            return false;
//        }
//
//        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
//            if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
//                return false;
//            }
//            if (visited[i][j]) {
//                return false;
//            }
//            if (board[i][j] != s.charAt(k)) {
//                return false;
//            } else if (k == s.length() - 1) {
//                return true;
//            }
//            visited[i][j] = true;
//            boolean result = false;
//            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
//            for (int[] dir : directions) {
//                int newi = i + dir[0], newj = j + dir[1];
//                boolean flag = check(board, visited, newi, newj, s, k + 1);
//                if (flag) {
//                    result = true;
//                    break;
//                }
//            }
////        boolean a = check(board, visited, i-1, j, s, k + 1);
////        if (a) {
////            result = true;
////        }
////        boolean b = check(board, visited, i+1, j, s, k + 1);
////        if (b) {
////            result = true;
////        }
////        boolean c = check(board, visited, i, j-1, s, k + 1);
////        if (c) {
////            result = true;
////        }
////        boolean d = check(board, visited, i, j+1, s, k + 1);
////        if (d) {
////            result = true;
////        }
//            visited[i][j] = false;
//            return result;
//        }
//
    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new P剑指Offer12矩阵中的路径().new Solution();
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        System.out.println(solution.exist(board, "ABCB"));
//        char[][] board = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        System.out.println(solution.exist(board, "ABCCED"));
    }
}